package com.leet.code.simple_array;

import java.util.HashMap;
import java.util.Map;

/**
 * @description: 1160.拼写单词
 * @author: WYG
 * @time: 2020/12/20 11:06
 */

public class CountCharacters {
    /**
     * 执行用时：62 ms, 在所有 Java 提交中击败了20.81%的用户
     * 内存消耗：39 MB, 在所有 Java 提交中击败了69.93%的用户
     * @param words
     * @param chars
     * @return
     */
    public int countCharacters(String[] words, String chars) {
        //存放最终的返回结果
        int res = 0;
        //存放给定的chars中字母出现的次数
        Map<Character, Integer> charsMap = new HashMap<>();
        //统计给定chars中字母出现的次数,并将其放入map中
        for (int i = 0; i < chars.length(); i++) {
            charsMap.put(chars.charAt(i), charsMap.getOrDefault(chars.charAt(i), 0) + 1);
        }
        //遍历words数组,找出可以被给定chars拼写出来的单词
        for (int j = 0; j < words.length; j++) {
            //标志,如果该单词可以被拼写则为true,否则位false,用于决定是否将该字符串的长度加入结果中
            boolean flag = true;
            //获取字符串
            String word = words[j];
            //存放字符串中字母出现次数的临时map
            Map<Character, Integer> wordMap = new HashMap<>();
            //统计字符串中字母出现的次数
            for (int k = 0; k < word.length(); k++) {
                char w = word.charAt(k);
                wordMap.put(w, wordMap.getOrDefault(w, 0) + 1);
            }
            //判断是否可以拼写
            for (int m = 0; m < word.length(); m++) {
                char temp = word.charAt(m);
                //如果字符串中某字母出现的次数大于给定chars中字母的出现次数,那么这个字符串无法被拼写,flag置为false
                if (wordMap.get(temp) > charsMap.getOrDefault(temp, 0)) {
                    flag = false;
                    break;
                }
            }
            // flag为true时证明字符串可以被拼写,其长度加入结果数组中
            if (flag) {
                res += word.length();
            }
        }
        return res;
    }

    /**
     * 执行用时：31 ms, 在所有 Java 提交中击败了38.96%的用户
     * 内存消耗：39.3 MB, 在所有 Java 提交中击败了34.68%的用户
     * @param words
     * @param chars
     * @return
     */
    public int Better_countCharacters(String[] words, String chars) {
        int res = 0;
        Map<Character, Integer> charsMap = new HashMap<>();
        for (int i = 0; i < chars.length(); i++) {
            charsMap.put(chars.charAt(i), charsMap.getOrDefault(chars.charAt(i), 0) + 1);
        }
        for (int j = 0; j < words.length; j++) {
            boolean flag = true;
            String word = words[j];
            Map<Character, Integer> wordMap = new HashMap<>();
            for (int k = 0; k < word.length(); k++) {
                char w = word.charAt(k);
                wordMap.put(w, wordMap.getOrDefault(w, 0) + 1);
                if (wordMap.get(w) > charsMap.getOrDefault(w, 0)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                res += word.length();
            }
        }
        return res;
    }
}
